package features.advance.leetcode.util;

import com.alibaba.fastjson.JSONArray;
import features.advance.leetcode.geometry.doublepointer.easy.ListNode;
import features.advance.leetcode.tree.model.TreeNode;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class TreeUtil {




    public static  TreeNode<Integer> stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }

        String[] parts = input.split(",");
        String item = parts[0];
        TreeNode<Integer> root = new TreeNode<>(Integer.parseInt(item),0);
        Queue<TreeNode<Integer>> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while(!nodeQueue.isEmpty()) {
            TreeNode<Integer> node = nodeQueue.remove();
            System.out.print(node.index+"==>");
            if (index == parts.length) {
                System.out.println();
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!"null".equals(item)) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode<>(leftNumber,index-1);
                System.out.print(index-1);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                System.out.println();
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!"null".equals(item)) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode<>(rightNumber,index-1);
                System.out.print(","+(index-1));
                nodeQueue.add(node.right);
            }
            System.out.println();
        }
        return root;
    }

    public static String booleanToString(boolean input) {
        return input ? "True" : "False";
    }

    /**
     * 有问题，不需要null作为站位符，得改成用栈来转换成树形式 TODO
     * @param integers
     * @param <E>
     * @return
     */
    public static<E> TreeNode<E> parseArray(List<Integer> integers){
        int k = 0;
        for (int i=0; i < integers.size(); i++) {
            Integer obj = integers.get(i);
            if(i % 2 != 0){
                if(obj == null){
                    k++;
                }
            }else{
                if(obj != null){
                    k--;
                }
            }
        }
        Map<Integer, TreeNode<E>> map = new HashMap<>(16);
        TreeNode<E> treeNode = new TreeNode();
        for (int i = integers.size() - 1; i >= 0; i--) {
            Integer integer = integers.get(i);
                   /*                   5
            1 3 4              3  |  6
            2 5 6             2|4  null|null
            3 7 8            1|null
            4 9 10
             */
            if (integer !=null)  {
                treeNode = new TreeNode(integer,i);
                map.put(i,treeNode);
                if(k==0){
                    if(map.get(i+2) != null){
                        //只有右侧节点
                        treeNode.setRight(map.get(i+2));
                        map.remove(i+2);
                    }
                }else{

                    if (map.get(i*2+1) !=null){
                        treeNode.setLeft(map.get(i*2+1));
                        map.remove(i*2+1);
                        // a[i] 的左子节点a[2*i+1]右子节点a[2*i+2]
                    }
                    if (map.get(i*2+2) !=null){
                        treeNode.setRight(map.get(i*2+2));
                        map.remove(i*2+2);
                    }
                }

            }
        }
        return treeNode;
    }

    public static<E> TreeNode<E> parseArray(int[] arr){
        List<Integer> integers = new ArrayList(Collections.singleton(arr));
        return parseArray(integers);
    }

    /**
     * 解析二叉查找树,数组结构特殊
     * @param arrStr
     * @return
     */
    public static<E> TreeNode<E> parseArray(String arrStr){
        if ("[]".equals(arrStr)) {
            return null;
        }
        List<Integer> integers = JSONArray.parseArray(arrStr, Integer.class);
        return parseArray(integers);
    }

    public static ListNode parseLinkedList(String arrStr){
        if("[]".equals(arrStr)){
            return null;
        }
        List<Integer> integers = JSONArray.parseArray(arrStr, Integer.class);
        ListNode head = new ListNode(integers.get(0));
        ListNode prev = head;
        for (int i = 1; i < integers.size(); i++) {
            ListNode listNode = new ListNode(integers.get(i));
            prev.next = listNode;
            prev = listNode;
        }
        return head;
    }
    public static void main(String[] args) {
        String str = "[41,37,44,24,39,42,48,1,35,38,40,null,43,46,49,0,2,30,36,null,null,null,null,null,null,45,47,null,null,null,null,null,4,29,32,null,null,null,null,null,null,3,9,26,null,31,34,null,null,7,11,25,27,null,null,33,null,6,8,10,16,null,null,null,28,null,null,5,null,null,null,null,null,15,19,null,null,null,null,12,null,18,20,null,13,17,null,null,22,null,14,null,null,21,23]";
        str = "[1,2,3]";
        TreeNode treeNode = parseArray(str);
        System.out.println(treeNode);
        try{
            Integer.parseInt("null");
        }catch(Exception e){
            System.err.println(e.getMessage());
        }finally{

        }
        System.out.println("请输入：");
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line = null;
        try{
            while((line = in.readLine())!=null){
                if("exit".equals(line)){
                    break;
                }
                System.out.println(line);
            }
        }catch(Exception e){

        }finally{
            try {
                in.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }
    public static void preorder(TreeNode root){
        if(root != null){
            System.out.print(root.val+",");
            preorder(root.left);
            preorder(root.right);
        }else{
            System.out.print("null,");
        }
    }
    public static void  cenorder(TreeNode root){
        if(root != null){
            cenorder(root.getLeft());
            System.out.print(root.getVal());
            cenorder(root.getRight());
        }
    }
    public static void postorder(TreeNode root){
        if(root != null){
            postorder(root.getRight());
            postorder(root.getLeft());
            System.out.print(root.getVal());
        }
    }

    /**
     * DLR--前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面）
     * @param node
     */
    private static void pre_order(TreeNode<Integer> node,Set<Integer> set){
        if(set == null){
            set = new HashSet<>();
            System.out.println("前序遍历：");
            System.out.print("[");
        }

        if(node == null){
            return;
        }
        if (!set.contains(node.val)){
            set.add(node.val);
        }
        System.out.print(node.val+",");


        pre_order(node.left,set);
        pre_order(node.right,set);
        if(set.contains(node.val)){
            set.remove(node.val);
        }
        if(set.isEmpty()){
            System.out.println("]");
        }


    }
    public static void pre_order(TreeNode node){
        pre_order(node,null);
    }

    /**
     * LDR--中序遍历（根在中间，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）
     * @param node
     */
    private static void middle_order(TreeNode node,StringBuilder sb){
        if(sb.toString().equals("")){
            System.out.println("中序遍历：");
            sb.append("[");
        }

        if(node == null){
            return;
        }

        middle_order(node.left,sb);
        sb.append(node.val+",");
        middle_order(node.right,sb);
    }
    public static void middle_order(TreeNode node){
        StringBuilder sb = new StringBuilder();
        middle_order(node,sb);
        sb.replace(sb.lastIndexOf(","),sb.lastIndexOf(",")+1,"]");
        System.out.println(sb);
    }

    public static String morder(TreeNode node){
        String morder = morder(node,false);
        return "["+new String(morder.toCharArray(),0,morder.lastIndexOf(","))+"]";
    }

    private static String morder(TreeNode node,boolean fummy){
        if(node == null){
            return "";
        }
        return morder(node.left,false) + node.val+","+morder(node.right,false);
    }

    /**
     * LRD--后序遍历（根在后，从左至右， 一棵树的左子树永远在右子树前面，右子树永远在根前面）
     * @param node
     */
    private static void post_order(TreeNode<Integer> node, Set<Integer> set){
        if(set == null){
            set = new HashSet<>();
            System.out.println("后序遍历：");
            System.out.print("[");
        }

        if(node == null){
            return;
        }

        if (!set.contains(node.val)){
            set.add(node.val);
        }
        post_order(node.left,set);
        post_order(node.right,set);
        if(set.contains(node.val)){
            set.remove(node.val);
        }
        if(set.isEmpty()){
            System.out.println(node.val+"]");
        }else{
            System.out.print(node.val+",");
        }


    }
    public static void post_order(TreeNode node){
        post_order(node,null);
    }


}
